package leetcode005;

import java.util.ArrayList;
import java.util.List;

/**
 * https://leetcode.cn/problems/longest-palindromic-substring/description/
 *
 * 给你一个字符串 s，找到 s 中最长的回文子串
 * 回文：如果字符串向前和向后读都相同，则它满足 回文性。
 * 子串：子字符串 是字符串中连续的 非空 字符序列。
 */
public class Study005 {

    /**
     * 动态规划
     * @param s
     * @return
     */
    public String longestPalindrome(String s) {
        int begin = 0;
        int maxLength = 1;

        //s长度只有1的情况
        if (s.length() == 1) {
            return s;
        }

        boolean[][] dp = new boolean[s.length()][s.length()];
        char[] chars = s.toCharArray();
        //初始化dp[i][i]，即单个字符都是回文子串
        for (int i = 0; i < s.length(); i++) {
            dp[i][i] = true;
        }
        //charNum是回文子串的长度，从2到s.length都要试一遍。看看是否有此长度的回文子串
        for (int charNum = 2; charNum <= s.length(); charNum++) {
            //字符串左指针
            for (int left = 0; left < s.length(); left++) {
                //右指针=左指针+字符个数-1
                int right = left + charNum - 1;
                //右指针越界了就继续下一次循环
                if (right >= s.length()) {
                    continue;
                }
                if (chars[left] == chars[right]) {
                    if (charNum < 3) {
                        dp[left][right] = true;
                    } else {
                        dp[left][right] = dp[left + 1][right - 1];
                    }
                } else {
                    dp[left][right] = false;
                }
                if (dp[left][right]) {
                    if (maxLength < right - left + 1) {
                        maxLength = right - left + 1;
                        begin = left;
                    }
                }
            }
        }
        return s.substring(begin, begin + maxLength);
    }


    /**
     * 中心拓展法
     * @param s
     * @return
     */
    public String longestPalindrome2(String s) {
        char[] chars = s.toCharArray();
        int center = 0;
        int maxLength = 0;
        for (int i = 0; i < chars.length; i++) {
            int m1 = expandAroundCenter(chars, i, i, 0);
            int m2 = expandAroundCenter(chars, i, i + 1, 0);
            if (m1 > maxLength) {
                maxLength = m1;
                center = i;
            }
            if (m2 > maxLength) {
                maxLength = m2;
                center = i;
            }
        }
        //偶数情况
        if (maxLength % 2 == 0) {
            return s.substring(center - maxLength/2 + 1, center + maxLength/2 +1);
        } else {
            return s.substring(center - maxLength/2, center + maxLength/2 +1);
        }
    }

    /**
     * 从中心出发往两边拓展
     * @return
     */
    private int expandAroundCenter(char[] chars, int left, int right, int maxLength) {
        //左指针或右指针超过边界则退出
        if (left < 0 || right >= chars.length) {
            return maxLength;
        }
        //拓展后两个字符相等，最大子串长度+1，并继续拓展
        if (chars[left] == chars[right]) {
            //左右指针指向同一个字符时maxLength增加1
            int increment = 1;
            //左右指针不指向同一个位置则maxLength+2
            if (left != right) {
                increment = 2;
            }
            maxLength = expandAroundCenter(chars, left - 1, right + 1,
                    maxLength + increment);
        }
        return maxLength;
    }


    /**
     * manacher算法
     * @param s
     * @return
     */
    public String longestPalindrome3(String s) {
        char[] chars = s.toCharArray();
        //初始化列表，向列表中添加#，通过#解决奇偶数的问题
        StringBuffer t = new StringBuffer("#");
        for (int i = 0; i < s.length(); ++i) {
            t.append(s.charAt(i));
            t.append('#');
        }
        t.append('#');
        s = t.toString();

        int[] arms = new int[s.length()];
        int maxLength = 0, maxCenter = 0, maxRight = 0, center = 0;
        for (int i = 0; i < s.length(); i++) {
            int length = 0;
            //如果i超过了mixRight
            if ( i >= maxRight) {
                //从i出发拓展
                length = expand(s, i, i);
            } else {
                //以maxCenter为中心，i的对称点
                int mirror = maxCenter - (i - maxCenter);
                //最小臂长=min（mirror的臂长，i到maxRight的距离）
                int lessHalfLength = Math.min(arms[mirror], maxRight - i);
                length = expand(s, i - lessHalfLength, i + lessHalfLength);
            }
            //更新最大长度和最大长度对应的中心点
            if (length > maxLength) {
                maxLength = length;
                center = i;
            }
            //臂长
            int arm = length / 2;
            //更新臂长数组
            arms[i] = arm;
            //如果right的最大边界更新了，maxCenter也要更新
            if (i + arm > maxLength) {
                maxRight = i + arm;
                maxCenter = i;
            }
        }
        StringBuffer ans = new StringBuffer();
        for (int i = (center - maxLength/2); i <= (center + maxLength/2); ++i) {
            if (s.charAt(i) != '#') {
                ans.append(s.charAt(i));
            }
        }
        return ans.toString();
    }

    private int expand(String s, int left, int right) {
        while (left >= 0 && right < s.length()
                && s.charAt(right) == s.charAt(left)) {
            --left;
            ++right;
        }
        return (right - left) - 1;
    }


    /**
     * manacher 官方题解
     * @param s
     * @return
     */
    public String longestPalindrome4(String s) {
        int start = 0, end = -1;
        StringBuffer t = new StringBuffer("#");
        for (int i = 0; i < s.length(); ++i) {
            t.append(s.charAt(i));
            t.append('#');
        }
        t.append('#');
        s = t.toString();

        List<Integer> arm_len = new ArrayList<Integer>();
        int maxRight = -1, maxCenter = -1;
        for (int i = 0; i < s.length(); ++i) {
            int cur_arm_len;
            if (maxRight >= i) {
                int i_sym = maxCenter * 2 - i;
                int min_arm_len = Math.min(arm_len.get(i_sym), maxRight - i);
                cur_arm_len = expand2(s, i - min_arm_len, i + min_arm_len);
            } else {
                cur_arm_len = expand2(s, i, i);
            }
            //arm添加到臂长列表
            arm_len.add(cur_arm_len);
            //如果right的最大边界更新了，maxCenter也要更新
            if (i + cur_arm_len > maxRight) {
                maxCenter = i;
                maxRight = i + cur_arm_len;
            }
            //更新最长回文子串的起始位置
            if (cur_arm_len * 2 + 1 > end - start) {
                start = i - cur_arm_len;
                end = i + cur_arm_len;
            }
        }

        StringBuffer ans = new StringBuffer();
        for (int i = start; i <= end; ++i) {
            if (s.charAt(i) != '#') {
                ans.append(s.charAt(i));
            }
        }
        return ans.toString();
    }

    public int expand2(String s, int left, int right) {
        while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
            --left;
            ++right;
        }
        return (right - left - 2) / 2;
    }


    public static void main(String[] args) {
        Study005 study005 = new Study005();
        String result = "";
        long start = 0, end = 0;

        start = System.currentTimeMillis();
        for (int i = 0; i < 100; i++) {
            result = study005.longestPalindrome4("babad");
            System.out.println(result + ":" + result.equals("bab"));
            result = study005.longestPalindrome4("b");
            System.out.println(result + ":" + result.equals("b"));
            result = study005.longestPalindrome4("bb");
            System.out.println(result + ":" + result.equals("bb"));
            result = study005.longestPalindrome4("badada");
            System.out.println(result + ":" + result.equals("adada"));
            result = study005.longestPalindrome4("cbbd");
            System.out.println(result + ":" + result.equals("bb"));
        }
        end = System.currentTimeMillis();
        System.out.println("**************longestPalindrome4 took " + (end - start) + "ms**************");

        start = System.currentTimeMillis();
        for (int i = 0; i < 100; i++) {
            result = study005.longestPalindrome3("babad");
            System.out.println(result + ":" + result.equals("bab"));
            result = study005.longestPalindrome3("b");
            System.out.println(result + ":" + result.equals("b"));
            result = study005.longestPalindrome3("bb");
            System.out.println(result + ":" + result.equals("bb"));
            result = study005.longestPalindrome3("badada");
            System.out.println(result + ":" + result.equals("adada"));
            result = study005.longestPalindrome3("cbbd");
            System.out.println(result + ":" + result.equals("bb"));
        }
        end = System.currentTimeMillis();
        System.out.println("**************longestPalindrome3 took " + (end - start) + "ms**************");



        for (int i = 0; i < 100; i++) {
            result = study005.longestPalindrome3("babad");
            System.out.println(result + ":" + result.equals("bab"));
            result = study005.longestPalindrome3("b");
            System.out.println(result + ":" + result.equals("b"));
            result = study005.longestPalindrome3("bb");
            System.out.println(result + ":" + result.equals("bb"));
            result = study005.longestPalindrome3("badada");
            System.out.println(result + ":" + result.equals("adada"));
            result = study005.longestPalindrome3("cbbd");
            System.out.println(result + ":" + result.equals("bb"));
        }
        end = System.currentTimeMillis();
        System.out.println("**************longestPalindrome3 took " + (end - start) + "ms**************");

        start = System.currentTimeMillis();
        for (int i = 0; i < 100; i++) {
            result = study005.longestPalindrome4("babad");
            System.out.println(result + ":" + result.equals("bab"));
            result = study005.longestPalindrome4("b");
            System.out.println(result + ":" + result.equals("b"));
            result = study005.longestPalindrome4("bb");
            System.out.println(result + ":" + result.equals("bb"));
            result = study005.longestPalindrome4("badada");
            System.out.println(result + ":" + result.equals("adada"));
            result = study005.longestPalindrome4("cbbd");
            System.out.println(result + ":" + result.equals("bb"));
        }
        end = System.currentTimeMillis();
        System.out.println("**************longestPalindrome4 took " + (end - start) + "ms**************");
    }
}
